package com.Oct_TwentyTwo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 685. 冗余连接 II
 * 在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
 *
 * 输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
 *
 * 结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
 *
 * 返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/redundant-connection-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/22 17:30
 */

public class Solution685 {

    /**
     * 标准并查集
     */
    private static final int  N= 1010;
    int[] father=new int[N];
    int n;
    void init()
    {
        for (int i = 0; i < N; i++) {
            father[i]=i;
        }
    }

    int find(int u){
        return u==father[u]?u:(father[u]=find(father[u]));
    }

    void union(int u,int v){
        u=find(u);
        v=find(v);
        if (u==v) return;
        father[v]=u;
    }

    boolean same(int u,int v){
        u=find(u);
        v=find(v);
        return u==v;
    }

    /**
     * 在有向图中找到删除的边，使其变成树
     * @param edges
     * @return
     */
    int[] getRemoveEdge(int[][] edges){
        init();
        for (int i = 0; i < edges.length; i++) {
            if (same(edges[i][0],edges[i][1]))
            {
                return edges[i];
            }
            union(edges[i][0],edges[i][1]);
        }
        return new int[]{};
    }

    /**
     * 查看删了这条边能否成树
     * @param edges
     * @param deleteTage
     * @return
     */
    boolean isTreeAfterRemoveEdge(int[][] edges,int deleteTage){
        init();
        for (int i = 0; i < edges.length; i++) {
            if (i==deleteTage) continue;
            if (same(edges[i][0],edges[i][1]))
            {
                return false;
            }
            union(edges[i][0],edges[i][1]);
        }
        return true;
    }


    public int[] findRedundantDirectedConnection(int[][] edges) {
        int[] inDegree=new int[N];
        n=edges.length;
        for (int i = 0; i < n; i++) {
            inDegree[edges[i][1]]++;
        }

        List<Integer> list=new ArrayList<>();
        for (int i=n-1;i>=0;i--)
        {
            if (inDegree[edges[i][1]]==2)
            {
                list.add(i);
            }
        }
        System.out.println(list.size());
        if (list.size()>0)
        {
            if (isTreeAfterRemoveEdge(edges,list.get(0)))
            {
                return edges[list.get(0)];
            }else if (isTreeAfterRemoveEdge(edges,list.get(1)))
            {
                return edges[list.get(1)];
            }
        }
        return getRemoveEdge(edges);
    }

    public static void main(String[] args) {
        Solution685 solution685=new Solution685();
        System.out.println(Arrays.toString(solution685.findRedundantDirectedConnection(new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 1}, {1, 5}})));
    }

}
